package codeTop;

public class q236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return res;
    }
    TreeNode res = null;
    boolean dfs(TreeNode node, TreeNode p, TreeNode q){
        if (res != null) {
            return false;
        }
        int num = 0;
        if (node.left != null) {
            num+=dfs(node.left,p,q)?1:0;
        }
        if (node.right != null) {
            num+=dfs(node.right,p,q)?1:0;
        }
        if (node.equals(p) || node.equals(q)) {
            num+=1;
        }
        if (num == 2) {
            res = node;
        }
        if (num >= 1) {
            return true;
        }else {
            return false;
        }
    }

    public static void main(String[] args) {
        q236 q = new q236();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        TreeNode p = root.left;
        root.right = new TreeNode(1);

        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);

        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        TreeNode q1 = root.left.right.right;
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        q.lowestCommonAncestor(root,p,q1);
    }
}
